package lc20240526;

import java.util.*;
import java.util.stream.Stream;

//452.用最少数量的箭引爆气球
public class Arrow {
    public static void main(String[] args) {
        int[][] array = {
                {-1,1},
                {0,1},
                {2,3},
                {1,2}
        };
        int[][] array1={
                {-2147483646, -2147483645},
                {2147483646, 2147483647}
        };
        int[][] array2={
                {1,2},
                {4,5},
                {1,5}
        };
        int[][] array3={
                {3, 9},
                {7, 12},
                {3, 8},
                {6, 8}, {9, 10}, {2, 9}, {0, 9}, {3, 9}, {0, 6}, {2, 8}
        };
        int[][] array4={
                {9, 12}, {1, 10}, {4, 11}, {8, 12}, {3, 9}, {6, 9}, {6, 7}
        };
        long l = System.currentTimeMillis();
        System.out.println(findMinArrowShotsGreed(array1));
        long l1 = System.currentTimeMillis();
        System.out.println(l1-l);
    }
    public static int findMinArrowShots(int[][] points) {
        //思路，首先是排序points数组，如果两个区间重合取交集，使得尽可能多的区间有交集。

        List<int[]> ints=new ArrayList<>();
        //排序。如果使用减法比较器(Arrays.sort(points, (o1, o2) -> o1[0] - o2[0]);)，可能会导致溢出问题。
        Arrays.sort(points,Comparator.comparingInt((int[] o)-> o[0]));

        if (points.length==1){
            return 1;
        }
        int[] curInt=points[0];
        ints.add(curInt);
        int i=0;
        while (i<points.length){
            //当前区间的下限
            int curEnd=curInt[1];
            int nextStart=points[i][0];
            int nextEnd=points[i][1];
            if (nextStart<=curEnd){
//                curInt=new int[]{nextStart,Math.min(nextEnd,curEnd)};
                curInt=new int[]{nextStart,nextEnd<curEnd?nextEnd:curEnd};
//                ints.add(curInt);
            }
            else{
                curInt=points[i];
                ints.add(curInt);
            }
            i++;
        }
        ints.stream().map(Arrays::toString).forEach(System.out::println);
//        if (ints.isEmpty()){
//            return points.length;
//        }
        return ints.size();
    }

    //贪心算法
    public static int findMinArrowShotsGreed(int[][] points){
        if (points.length==0||points==null){
            return 0;
        }
        //排序
        Arrays.sort(points, (Comparator.comparingInt(o -> o[1])));
        int arrowCount=1;
        int end=points[0][1];
        for (int i = 0; i < points.length; i++) {
            //前一个区间末尾小于后一个区间开始
            if (end<points[i][0]){
                arrowCount++;
                end=points[i][1];
            }
        }
        return arrowCount;
    }
}
